/**
 * FileName: Exercise1605.c
 * -------------------------------------------------------------------------------------------------------
 * 16.5 Give the contents of the `3-4-5-6` tree that results when you insert the keys
 * `E A S Y Q U E S T I O N W I T H P L E N T Y O F K E Y S` in that order into an initially empty tree.
 *
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

//Item相关
typedef char Key;
typedef int Value;
typedef struct Item* Item;

struct Item {
    Key key;
    Value value;
};

//注意：这些宏的参数是 Item* 类型，因此比较的是其内部的 key 成员
#define key(A) (A->key)
#define value(A) (A->value)
#define less(A, B)  ((A) < (B))
#define eq(A, B)    ((A) == (B))
#define exch(A, B) { Item t = A; A = B; B = t; }
#define NULLitem NULL

#define M 6 //B树的阶

//STnode相关
typedef struct STnode* link;
typedef struct {
    Key key;
    union {
        link next;
        Item item;
    } ref;
} entry;

struct STnode {
    entry b[M];
    int m;
};

static link head;
static int N;
static int H;


//辅助函数声明
link NEW();
Item searchR(link, Key, int);
link insertR(link, Item, int);
link split(link);

//符号表操作声明
void STinit();
Item STsearch(Key);
void STinsert(Item);

//辅助函数实现
link NEW() {
    link x = malloc(sizeof(*x));
    x->m = 0;
    return x;
}

link split(link h) {
    int j;
    link t = NEW();
    int split_idx = M/2; // 分裂点索引，也是拷贝键的索引
    for (j = 0; j < (M - split_idx); j++) {
        t->b[j] = h->b[split_idx+j];
    }
    t->m = M - split_idx;
    h->m = M/2;
    return t;
}

Item searchR(link h, Key v, int H) {
    int j;
    if (H == 0) {
        for (j = 0; j < h->m; j++) {
            if (eq(v, h->b[j].key)) {
                return h->b[j].ref.item;
            }
        }
    }
    if (H != 0) {
        for (j = 0; j < h->m; j++) {
            if ((j+1 == h->m) || less(v, h->b[j+1].key)) {
                return searchR(h->b[j].ref.next, v, H-1);
            }
        }
    }
    return NULLitem;
}

link insertR(link h, Item item, int H) {
    int i;
    int j;
    Key v = key(item);
    entry x;
    link t;
    link u;

    x.key = v;
    x.ref.item = item;

    if (H == 0) {
        for (j = 0; j < h->m; j++) {
            if (less(v, h->b[j].key)) {
                break;
            }
        }
    }

    if (H != 0) {
        for (j = 0; j < h->m; j++) {
            if ((j+1 == h->m) || less(v, h->b[j+1].key)) {
                t = h->b[j].ref.next;
                u = insertR(t, item, H-1);
                if (u == NULL) {
                    return NULL;
                }
                x.key = u->b[0].key;
                x.ref.next = u;
                j++;
                break;
            }
        }
    }

    (h->m)++;
    for (i = (h->m)-1; i > j; i--) {
        h->b[i] = h->b[i-1];
    }
    h->b[j] = x;
    if (h->m < M) {
        return NULL;
    }else {
        return split(h);
    }
}

//符号表操作实现
void STinit() {
    head = NEW();
    H = 0;
    N = 0;
}

Item STsearch(Key v) {
    return searchR(head, v, H);
}

void STinsert(Item item) {
    link t;
    link u = insertR(head, item, H);
    if (u == NULL) {
        N++;
        return;
    }
    t = NEW();
    t->m = 2;
    t->b[0].key = head->b[0].key;
    t->b[0].ref.next = head;
    t->b[1].key = u->b[0].key;
    t->b[1].ref.next = u;

    head = t;
    H++;
    N++;
}




//测试函数部分
Item createItem(Key, Value);
void test_insert();

int main(int argc, char *argv[]) {
    test_insert();
    return 0;
}

Item createItem(Key key, Value value) {
    Item x = malloc(sizeof(*x));
    x->key = key;
    x->value = value;
    return x;
}

void test_insert() {
    char keys[] = "EASYQUESTIONWITHPLENTYOFKEYS";
    // 计算数组中元素的数量
    int num_elements = sizeof(keys) / sizeof(keys[0]);
    STinit();
    for (int i = 0; i < num_elements-1; i++) {
        STinsert(createItem(keys[i], i+1));
    }

    assert(N == 28);
    assert(H == 2);

    printf("序列EASYQUESTIONWITHPLENTYOFKEYS\n");

    printf("-- 插入完成，节点总数 N = %d，B 树高度 H = %d\n", N, H);

    for (int i = 0; i < num_elements-1; i++) {
        Item found = STsearch(keys[i]);
        assert(key(found) == keys[i]);
    }
    printf("-- 所有插入的键均成功检索。\n");

}
